P2574 XOR的艺术

相同的题目：

• P2846 [USACO08NOV] Light Switching G - 洛谷 | 计算机科学教育新生态
• P 3870 [TJOI 2009] 开关 - 洛谷 | 计算机科学教育新生态
• LITE - Light Switching - 洛谷 | 计算机科学教育新生态
• P5057 [CQOI2006] 简单题 - 洛谷 | 计算机科学教育新生态

题意：

• 若 $op=0$，则表示将伤害串的 $[l,r]$ 区间内的 0 变成 1，1 变成 0。
• 若 $op=1$，则表示询问伤害串的 $[l,r]$ 区间内有多少个字符 1。

$2\le n,m\le 2\times {10}^5$，$0\le op\le 1$，$1\le l\le r\le n$，$S$ 中只含字符 0 和字符 1。

Solution

线段树区间修改(XOR) 典

query 函数不变，当一个区间反转时，只需要用区间长度减去区间和即可得到新的区间和。

（反转前+反转后）的区间和等于区间长度

#define lc u<<1
#define rc u<<1|1
int n, m;
int a[200010];
struct tr { //线段树
    ll l, r, sum, add;
}tr[800010];

void pushup(ll u) { //上传
    tr[u].sum = tr[lc].sum + tr[rc].sum;
}
void pushdown(ll u) { //下传
    if (tr[u].add) {
        tr[lc].sum = tr[lc].r - tr[lc].l + 1 - tr[lc].sum;
        tr[rc].sum = tr[rc].r - tr[rc].l + 1 - tr[rc].sum;
        tr[lc].add ^= 1;
        tr[rc].add ^= 1;
        tr[u].add = 0;
    }
}
void build(ll u, ll l, ll r) { //建树
    tr[u] = {l,r,a[l],0};
    if (l == r) return;
    ll m = l + r >> 1;
    build(lc, l, m);
    build(rc, m + 1, r);
    pushup(u);
}
void change(ll u, ll l, ll r) { //区修
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].sum = (tr[u].r - tr[u].l + 1) - tr[u].sum;
        // tr[u].add += k;
        tr[u].add ^= 1;
        return;
    }
    ll m = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    if (l <= m) change(lc, l, r);
    if (r > m) change(rc, l, r);
    pushup(u);
}
ll query(ll u, ll l, ll r) { //区查
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    ll m = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    ll sum = 0;
    if (l <= m) sum += query(lc, l, r);
    if (r > m) sum += query(rc, l, r);
    return sum;
}
void solve() {
    cin >> n >> m;string s;cin >> s;s = ' ' + s;
    for (int i = 1;i <= n;i++) {
        a[i] = s[i] - '0';
    }
    build(1, 1, n);
    while (m--) {
        int op, l, r;cin >> op >> l >> r;
        if (op == 0) {
            change(1, l, r);
        } else {
            cout << query(1, l, r) << '\n';
        }
    }
}